package dateStructure;

import sun.reflect.generics.tree.Tree;

import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;

//public class Search {
//    //顺序查找+二分查找
//    public static void main(String arg[]){
//        int nums[]={7,6,5,4,3,2,1};
//        Scanner scanner =new Scanner(System.in);
//        System.out.println("请输入要查找的元素：");
//        int n=scanner.nextInt();
//        Arrays.sort(nums);
//        System.out.println("排序后的数组为："+Arrays.toString(nums));
//        System.out.println("n为数组的第"+binarySearch(nums,n)+"个元素");
//    }
//
//    public static int binarySearch(int nums[],int n){//二分查找 需要先进行排序
//        int left=0;
//        int right=nums.length-1;
//        while (left<=right){
//            int mid=(left+right)>>1;
//            if(nums[mid]==n){
//                return mid+1;
//            }
//            else if(nums[mid]>n){
//                right=mid-1;
//            }
//            else{
//                left=mid+1;
//            }
//        }
//        return -1;
//    }
//}
//class Search1 {
//    //二叉搜索树算法
//    public static void main(String arg[]) {
//        Scanner scanner = new Scanner(System.in);
//        TNode MyT = null;
//        MyT = createTree(MyT);
//        System.out.print("该二叉搜索树的排序结果为：");
//        inOrder(MyT);
//        System.out.println();
//        System.out.print("请输入要查找的数据；");
//        int e = scanner.nextInt();
//        TNode s = searchTree(MyT, e);
//        if (s != null) {
//            System.out.println("在树中找到了该数据！");
//        } else {
//            System.out.println("未找到！");
//        }
//        System.out.print("请输入要删除的数据：");
//        e = scanner.nextInt();
//        MyT = deleteTree(MyT, e);
//        if (MyT != null) {
//            System.out.print("删除后的结果为：");
//            inOrder(MyT);
//            System.out.println();
//        } else {
//            System.out.println("被删除元素未找到！");
//        }
//    }
//
//    private static class TNode {
//        TNode left, right;
//        int val;
//    }
//
//    /**
//     * @param T 被删除数据的树
//     * @param e 被删除的数据
//     */
//    private static TNode deleteTree(TNode T, int e) {
//        if (T != null) {
//            TNode s;//指向当前节点
//            TNode f = null;//为s节点的父亲
//            TNode p = T;//p为根节点
//            TNode q = null;//为中间节点
//            while (p != null) {//开始找要被删除的节点
//                if (p.val == e) {//找到了要删除的节点
//                    break;
//                }
//                f = p;//f为被删除节点p的双亲
//                if (e < p.val) {
//                    p = p.left;
//                } else {
//                    p = p.right;
//                }
//            }
//            //退出了循环，有两种可能
//            //p==null或者p.val==e
//            if (p == null) {//如果找不到被删除的数据
//                return p;//直接返回
//            }
//            //找到了要被删除的数据
//            //开始判断属于哪种情况
//            if ((p.left != null) && (p.right != null)) {//第一种情况:即被删除节点左右孩子均不为空
//                q = p;//现在开始找被删除节点的直接前驱
//                s = p.left;//找到当前节点的左孩子开始找直接前驱
//                while (s.right != null) {
//                    q = s;//q为s的父亲
//                    s = s.right;//找到其左孩子那颗树的最右边的节点
//                }
//                p.val = s.val;//将最后所在的节点的值付给删除节点的直接前驱
//                if (p != q) {//说明其左孩子是有右孩子这种情况
//                    q.right = s.left;//将s下面的左孩子接到q上
//                } else {//如果其左孩子没有右孩子
//                    p.left = s.left;//，则直接把其左孩子作为直接前驱
//                }
//            } else {
//                if (p.right == null) {//即删除节点右孩子为空
//                    q = p;
//                    p = p.left;
//                } else if (p.left == null) {//删除节点左孩子为空
//                    q = p;
//                    p = p.right;
//                }
//                if (f == null) {//如果f为空，即被删除节点p为跟节点
//                    T=p;//则直接把当前p所在的位置（要删除节点的左孩子||右孩子）赋给T的位置，代替根
//                } else if (f.left == q) {//如果f的左孩子为要删除的节点
//                    f.left = p;
//                } else {//否则把p放到f的右孩子上
//                    f.right = p;
//                }
//            }
//        }
//        return T;
//    }
//
//    /**
//     * @param T 被找数据所在的树
//     * @param e 被找的数据
//     * @return 找到的树节点
//     */
//    public static TNode searchTree(TNode T, int e) {
//        TNode p = T;
//        if (p == null || p.val == e) {//如果当前节点为空，或者当前节点的值等于该数据
//            return p;//直接返回当前节点
//        } else if (e < p.val) {
//            return searchTree(T.left, e);//小于的话就往左找
//        }
//        return searchTree(T.right, e);//否则往右找
//    }
//
//    /**
//     * @param T 要创建的树节点
//     * @param e 要插入到树中的数据
//     * @return 创建好的树
//     */
//    private static TNode insertTree(TNode T, int e) {
//        if (T == null) {//如果当前还没有创建根节点
//            T = new TNode();
//            T.val = e;
//            T.left = T.right = null;//左右孩子都为空
//        } else {//否则已有根节点
//            if (e < T.val) {//如果当前插入数据小于当前节点的值
//                T.left = insertTree(T.left, e);//其数据插入到其左孩子上
//            } else if (e > T.val) {
//                T.right = insertTree(T.right, e);//否则插入到其右孩子上
//            }
//        }
//        return T;
//    }
//
//    private static TNode createTree(TNode T) {
//        Scanner scanner = new Scanner(System.in);
//        System.out.println("请依次输入每个数（-1为停止输入标志）：");
//        int e = scanner.nextInt();//输入当前要插入树中的数据
//        while (e != -1) {//如果插入数据一直不为-1 一直循环插入
//            T = insertTree(T, e);
//            e = scanner.nextInt();
//        }
//        return T;
//    }
//
//    public static void inOrder(TNode T) {
//        if (T != null) {
//            inOrder(T.left);
//            System.out.print(T.val + " ");
//            inOrder(T.right);
//        }
//    }
//}


//class Search2 {
//    //平衡二叉树删除算法
//    //69 25 80 16 56 75 90 30 78 85 98 82 -1
//    public static void main(String arg[]) {
//        TNode MyT = null;//像这种创建树的，一开始有可能是空树的，要初始化为空
//        MyT = createTree(MyT);
//        Scanner scanner = new Scanner(System.in);
//        System.out.print("请输入要删除的数据：");
//        int e = scanner.nextInt();
//        MyT = deleteTree(MyT, e);
//        if (MyT != null) {
//            System.out.print("删除后的结果为：");
//            System.out.println("平衡二叉树前序遍历为：");
//            preOrder(MyT);
//            System.out.println("平衡二叉树中序遍历为：");
//            inOrder(MyT);
//            System.out.println("平衡二叉树后序遍历为：");
//            postOrder(MyT);
//        } else {
//            System.out.println("被删除元素未找到！");
//        }
//    }
//
//    private static class TNode {
//        TNode left, right;
//        int val;//记录其每个点的数据
//        int height;//记录其每个节点的高度
//    }
//
//    public static int height(TNode T) {
//        if (T == null) {
//            return 0;//空节点的高度初始化为0
//        }
//        return T.height;
//    }
//
//    private static void updateHeight(TNode T) {
//        T.height = Math.max(height(T.left), height(T.right)) + 1;//每次返回的结果为左右孩子的高度最大值再加上1
//    }
//
//    private static TNode llTree(TNode T) {
//        TNode temp = T.left;//将A节点的左孩子赋个一个临时变量上，作为B
//        T.left = temp.right;//将B的右孩子，赋值到A的左孩子
//        temp.right = T;//将A赋值到B的右孩子的位置
//        //更新A与B的高度
//        updateHeight(T);
//        updateHeight(temp);
//        return temp;//返回当前的根为B
//    }
//
//    private static TNode rrTree(TNode T) {//与LL刚好相反
//        TNode temp = T.right;//将A节点的右孩子赋个一个临时变量上，作为B
//        T.right = temp.left;//将B的左孩子，赋值到A的右孩子
//        temp.left = T;//将A赋值到B的左孩子的位置
//        //更新A与B的高度D
//        updateHeight(T);
//        updateHeight(temp);
//        return temp;//返回当前的根为B
//    }
//
//    private static TNode rlTree(TNode T) {
//        T.right = llTree(T.right);//先将根A的左孩子作为根去做LL旋转
//        return rrTree(T);//然后再将A作为根再做RR旋转，从而的得到RL旋转的结果
//    }
//
//    private static TNode lrTree(TNode T) {
//        T.left = rrTree(T.left);//先将根A的右孩子作为根去做RR旋转
//        return llTree(T);//然后再将A作为根再做LL旋转，从而的得到LR旋转的结果
//    }
//
//    private static TNode adjustTree(TNode T) {
//        if (T != null) {
//            if (height(T.left) - height(T.right) == 2) {
//                if (height(T.left.left) >= height(T.left.right)) {//说明其左孩子的左子树比右子树大，需要调整
//                    T = llTree(T);//使用LL旋转
//                } else {
//                    T = lrTree(T);//使用L旋转
//                }
//            } else if (height(T.right) - height(T.left) == 2) {
//                if (height(T.right.right) >= height(T.right.left)) {//说明其右孩子的右子树比左子树大，需要调整
//                    T = rrTree(T);//使用RR旋转
//                } else {
//                    T = rlTree(T);//使用RL旋转
//                }
//            }
//            updateHeight(T);
//        }
//        return T;
//    }
//
//    /**
//     * @param s 堆栈中存的祖父，父亲，我
//     * @param T 当前二叉树的根节点
//     * @return 返回旋转好的根节点
//     */
//    private static TNode updateBalance(Stack<TNode> s, TNode T) {
//        while (!s.isEmpty()) {
//            TNode ff = s.pop();//从堆栈中取出栈顶元素，即祖父
//            updateHeight(ff);//更新祖父的高度
//            if (!s.isEmpty()) {//如果还有堆栈中还有父亲的话，继续出栈
//                TNode f = s.peek();//从堆栈中取出栈顶元素，即父亲
//                if (f.left == ff) {
//                    f.left = adjustTree(ff);//调整其左子树
//                } else {
//                    f.right = adjustTree(ff);
//                }
//            } else {
//                T = adjustTree(ff);
//            }
//        }
//        return T;
//    }
//
//    private static TNode deleteTree(TNode T, int e) {
//        if (T != null) {
//            TNode s;//指向当前节点
//            TNode f = null;//为s节点的父亲
//            TNode p = T;//p为根节点
//            TNode q = null;//为中间节点
//            Stack<TNode> st = new Stack<>();//用于存储父亲的节点，
//            while (p != null) {//开始找要被删除的节点
//                if (p.val == e) {//找到了要删除的节点
//                    break;
//                }
//                f = p;//f为被删除节点p的双亲
//                st.push(f);//把一路上往下走的父亲入栈
//                if (e < p.val) {
//                    p = p.left;
//                } else {
//                    p = p.right;
//                }
//            }
//            //退出了循环，有两种可能
//            //p==null或者p.val==e
//            if (p == null) {//如果找不到被删除的数据
//                return p;//直接返回
//            }
//            //找到了要被删除的数据
//            //开始判断属于哪种情况
//            if ((p.left != null) && (p.right != null)) {//第一种情况:即被删除节点左右孩子均不为空
//                q = p;//现在开始找被删除节点的直接前驱
//                st.push(p);//把找到的直接前驱入栈
//                s = p.left;//找到当前节点的左孩子开始找直接前驱
//                while (s.right != null) {
//                    q = s;//q为s的父亲
//                    s = s.right;//找到其左孩子那颗树的最右边的节点
//                }
//                p.val = s.val;//将最后所在的节点的值付给删除节点的直接前驱
//                if (p != q) {//说明其左孩子是有右孩子这种情况
//                    q.right = s.left;//将s下面的左孩子接到q上
//                    st.push(q);//把找到的直接前驱的父亲给入栈
//                } else {//如果其左孩子没有右孩子
//                    p.left = s.left;//，则直接把其左孩子作为直接前驱
//                }
//            } else {
//                if (p.right == null) {//即删除节点右孩子为空
//                    q = p;
//                    p = p.left;
//                } else if (p.left == null) {//删除节点左孩子为空
//                    q = p;
//                    p = p.right;
//                }
//                if (f == null) {//如果f为空，即被删除节点p为跟节点
//                    T = p;//则直接把当前p所在的位置（要删除节点的左孩子||右孩子）赋给T的位置，代替根
//                } else if (f.left == q) {//如果f的左孩子为要删除的节点
//                    f.left = p;
//                } else {//否则把p放到f的右孩子上
//                    f.right = p;
//                }
//            }
//            T = updateBalance(st, T);
//        }
//        return T;
//    }
//
//    /**
//     * @param T 要创建的树节点
//     * @param e 要插入到树中的数据
//     * @return 创建好的树
//     */
//    private static TNode insertTree(TNode T, int e) {
//        if (T == null) {//如果当前还没有创建根节点
//            T = new TNode();
//            T.val = e;
//            T.left = T.right = null;//左右孩子都为空
//            T.height = 1;//只有一个节点的时候，其高度初始化为1
//        } else {//否则已有根节点
//            if (e < T.val) {//如果当前插入数据小于当前节点的值
//                T.left = insertTree(T.left, e);//其数据插入到其左孩子上
//                if (height(T.left) - height(T.right) == 2) {//说明不是一棵平衡的二叉树 要进行旋转
//                    if (e < T.left.val) {//说明要进行LL旋转//
//                        T = llTree(T);
//                    } else {//说明要进行LR旋转 / \
//                        T = lrTree(T);
//                    }
//                }
//            } else if (e > T.val) {
//                T.right = insertTree(T.right, e);//否则插入到其右孩子上
//                if (height(T.right) - height(T.left) == 2) {//说明不是一棵平衡的二叉树 要进行旋转
//                    if (e < T.right.val) {//说明要进行RR旋转 \\
//                        T = rrTree(T);
//                    } else {//说明要进行RL旋转 \ /
//                        T = rlTree(T);
//                    }
//                }
//            }
//        }
//        updateHeight(T);
//        return T;
//    }
//
//    private static TNode createTree(TNode T) {
//        Scanner scanner = new Scanner(System.in);
//        System.out.println("请依次输入每个数（-1为停止输入标志）：");
//        int e = scanner.nextInt();//输入当前要插入树中的数据
//        while (e != -1) {//如果插入数据一直不为-1 一直循环插入
//            T = insertTree(T, e);
//            e = scanner.nextInt();
//        }
//        return T;
//    }
//
//    public static void preOrder(TNode T) {
//        if (T != null) {
//            System.out.println(T.val + "\t" + height(T));
//            preOrder(T.left);
//            preOrder(T.right);
//        }
//    }
//
//    public static void inOrder(TNode T) {
//        if (T != null) {
//            inOrder(T.left);
//            System.out.println(T.val + "\t" + height(T));
//            inOrder(T.right);
//        }
//    }
//
//    public static void postOrder(TNode T) {
//        if (T != null) {
//            postOrder(T.left);
//            postOrder(T.right);
//            System.out.println(T.val + "\t" + height(T));
//        }
//    }
//
//}
class Search3 {
    //哈希查找
    public static void main(String arg[]) {
        Scanner scanner = new Scanner(System.in);
        Hash MyH = new Hash();
        System.out.println("请依次输入12个数字存入到哈希表中：");
        for (int i = 0; i < 12; i++) {
            int x = scanner.nextInt();
            if (!insertHash(MyH, x)) {
                System.out.println("插入失败！");
                return;
            }
        }
        System.out.println("输入哈希表：");
        print(MyH);
    }

    private static final int m = 15;
    private static int sum=0;
    private static class Hash {
        int H[] = new int[m];
        int n[] = new int[m];
    }

    private static boolean insertHash(Hash h, int x) {
        int h0 = x % 13;
        int hi;
        sum = 1;
        if (h.H[h0] == 0) {//说明该位置没有元素
            h.H[h0] = x;
            h.n[h0] = sum;
            return true;
        } else {//说明该位置已经被占了
            hi = doubleSearch(h,h0, x);
            if (hi == -1) {
                return false;
            }
            //说明二次探测找到了
            h.H[hi]=x;
            h.n[hi]=sum;
        }
        return false;
    }

    /**
     *
     * @param h 该哈希表的元素及其检测次数
     * @param x 要插入到哈希表中的元素
     * @return
     */
    private static int doubleSearch(Hash h,int h0, int x) {
        for(int i=0;i<(m>>1);i++){//从0一直开始找到m/2
            sum++;
            int hi=(i*i+h0)%13;
            //向左开始检测
            if(h.H[hi]==0){
                //说明该位置没有元素，可以插入
                h.H[hi]=x;
                h.n[hi]=sum;
                return hi;
            }
            else if(h.H[hi]==x){
                //说明找到了自己 直接返回
                return hi;
            }
            //说明左边没有找到，向右开始检测
            sum++;
            hi=(-i*i+h0);
            if(hi<0){
                hi+=m;
            }
            if(h.H[hi]==0){
                //说明该位置没有元素，可以插入
                h.H[hi]=x;
                h.n[hi]=sum;
                return hi;
            }
            else if(h.H[hi]==x){
                //说明找到了自己 直接返回
                return hi;
            }
        }
        return -1;
    }

    public static void print(Hash h) {
        for (int i = 0; i < 12; i++) {
            System.out.print(h.H[i] + "\t");
        }
        for (int i = 0; i < 12; i++) {
            System.out.print(h.n[i] + "\t");
        }
    }
}
